package com.example.Arithmetic.Arithmetic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 日期：2023/10/14
 * 时间：12:27
 * 描述：深度二叉树前中后序遍历混合
 */
public class DeepTree {
    public List list1 = new ArrayList();  //前序
    public List list2 = new ArrayList();   //中序
    public List list3 = new ArrayList();    //后序
//    循环遍历

    public void preorderTraversal1(TreeNode root) {
        TreeNode curr = root;
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        TreeNode p = null;
        while (!linkedList.isEmpty() || curr != null) {
            if (curr != null) {
                linkedList.push(curr);
                list1.add(curr.val);
//                待处理左字树
                curr = curr.left;
            } else {
                TreeNode peek = linkedList.peek();
//                右子树为空
                if (peek.right == null) {
                    p = linkedList.pop();
                    list2.add(p.val);
                    list3.add(p.val);
//                    右子树处理过
                } else if (peek.right == p) {
                    p = linkedList.pop();
                    list3.add(p.val);
//                    待处理右子树
                } else {
                    list2.add(linkedList.peek().val);
                    curr = peek.right;
                }
            }
        }
    }

    //    递归

    public List<Integer> preorderTraversal2(TreeNode root) {
        List list = new ArrayList();
        if (root == null) {
            return list;
        }
        list1.add(root.val);
        preorderTraversal2(root.left);
        list2.add(root.val);
        preorderTraversal2(root.right);
        list3.add(root.val);
        return list;
    }

    public static void main(String[] args) {
        DeepTree deepTree = new DeepTree();
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null)
                , 1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6)));
        deepTree.preorderTraversal1(root);
        System.out.println("前序" + deepTree.list1);
        System.out.println("中序" + deepTree.list2);
        System.out.println("后序" + deepTree.list3);
        deepTree.preorderTraversal2(root);
        System.out.println("前序" + deepTree.list1);
        System.out.println("中序" + deepTree.list2);
        System.out.println("后序" + deepTree.list3);
    }
}

